package linklist;

import org.junit.Test;

//删除链表的倒数第n个节点
public class LeetCode_19 {
    public class ListNode {
        int val;
        ListNode next;
        ListNode() {}
        ListNode(int val) { this.val = val; }
        ListNode(int val, ListNode next) { this.val = val; this.next = next; }
    }

    public ListNode removeNthFromEnd(ListNode head, int n) {
       return  solution_1(head,n);
    }

    //两次循环完成
    private ListNode solution_1(ListNode head, int n) {
        //1. 计算长度
        ListNode tempHead = head;
        int length=0;
        while (tempHead!=null){
            length++;
            tempHead=tempHead.next;
        }
        System.out.println(length);//2

        if (length==1 && n==1){
            return null;
        }

        //2. 计算删除前一个位置
        int location = length-n-1;    //1
        if (location<0){
            head=head.next;
            return head;
        }
        tempHead = head;
        while (location!=0){
            location--;
            tempHead=tempHead.next;
        }
        System.out.println(tempHead.val);

        //3. 修改指针
        tempHead.next=tempHead.next.next;

        return head;


    }


    //两次循环完成
    private ListNode solution_2(ListNode head, int n) {

        //1. 定义快慢指针
        ListNode fast=head,slow=head;

        //2. 快指针移动
        int size=n+1;
        while (fast!=null&&size>0){
            size--;
            fast=fast.next;
        }
        if (size>0){
            head=head.next;
            return head;
        }

        //3. 遍历
        while (fast!=null){
            fast=fast.next;
            slow=slow.next;
        }

        //4. 修改指针
        slow.next=slow.next.next;

        return head;


    }



}
